package com.tree;


/**
 * 〈线段树〉
 *
 * @author Demi
 * @createDate 2020/2/13
 */
public class SegmentTree<E> {
    private E[] data;//接收用户传进来的数组
    private E[] tree;//线段树
    private Merger<E> merge;

    //初始化数组和线段树并构建线段树
    public SegmentTree(E[] arr,Merger<E> merge) {
        //初始化Merge
        this.merge=merge;
        data=(E[])new Object[arr.length];//声明空间大小
        //给data填值
        for(int i=0;i<arr.length;i++){
            data[i]=arr[i];
        }
        //声明线段树空间大小
        tree=(E[])new Object[9];
        //构建线段树
        buildSegmentTree(0,0,data.length-1);
    }
    //
    public  E query(int queryL,int queryR){
        if(queryL<0||queryL>=data.length||queryR<0||
                queryR>=data.length||queryR<queryL){
            throw new IllegalArgumentException("参数错误");
        }
        return queryRange(0,0,data.length-1,queryL,queryR);

    }
    //执行真正的查询
    private E queryRange(int index,int l,int r,int queryL,int queryR){
        E result=null;
        if(l==queryL&&r==queryR){
            return tree[index];
        }
        int left=leftChild(index);//根据index得到左孩子的索引赋给left
        int right=rightChild(index);//根据index得到右孩子的索引赋给right
        int mid=l+(r-l)/2;//中间边界
        if(queryL>=mid+1){
            result=queryRange(right,mid+1,r,queryL,queryR);
        }else if(queryR<=mid){
            result=queryRange(left,l,mid,queryL,queryR);
        }else{
            E a=queryRange(left,l,mid,queryL,mid);
            E b=queryRange(right,mid+1,r,mid+1,queryR);
            result=merge.merge(a,b);

        }
        return result;

    }
    //左孩子的索引
    private int leftChild(int index){
        return 2*index+1;
    }
    //右孩子的索引
    private int rightChild(int index){
        return 2*index+2;
    }
    //构建线段树//index当前位置下标//l左边界，r右边界[l,r]
    public void buildSegmentTree(int index,int l,int r){
        if(l==r){
            tree[index]=data[l];
            return ;
        }
        int left=leftChild(index);//根据index得到左孩子的索引赋给left
        int right=rightChild(index);//根据index得到右孩子的索引赋给right
        int mid=l+(r-l)/2;//中间边界   [left,right]
        //构建左孩子的区间
        buildSegmentTree(left,l,mid);//[index,l,r]
        //构建右孩子的区间
        buildSegmentTree(right,mid+1,r);//[index,l,r]
        //求和
        tree[index]=merge.merge(tree[left],tree[right]);
    }

    public void set(int index,E value){
        if(index<0||index>=data.length){
            return;
        }
        setValue(0,0,data.length-1,index,value);
    }

    /**在以tree中位置为treeIndex为根节点，而且该节点对应的data中的范围为[treeLeft,treeRight] 下，<br>
     * 修改data中index的元素，设置新的值为value
     * @param treeIndex
     * @param treeLeft
     * @param treeRight
     * @param index
     * @param value
     */
    public void setValue(int treeIndex,int treeLeft,int treeRight,int index,E value){
        if(treeLeft==treeRight){
            tree[treeIndex]=value;
            return;
        }
        int leftChildIndex=leftChild(treeIndex);
        int rightChildIndex=rightChild(treeIndex);
        int mid=treeLeft+(treeRight-treeLeft)/2;
        if(index<=mid){
            setValue(leftChildIndex, treeLeft, mid, index, value);
        }
        else{
            setValue(rightChildIndex, mid+1, treeRight, index, value);
        }
        tree[treeIndex]=merge.merge(tree[leftChildIndex], tree[rightChildIndex]);
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null) {
                sb.append(tree[i]);
            } else {
                sb.append("null");
            }
            //到最后一个之前，拼接逗号
            if (i != tree.length - 1) {
                sb.append(",");
            }

        }
        sb.append("]");
        return sb.toString();
    }
}


